# coding: utf-8
# 冒泡排序实现

#把最小的沉到low的位置
#[low,high]
def bubble(lst,low,high):
    swap = False
    # high~low, 交换可以得到最小的数
    for i in range(high,low,-1):
        # 如果有逆序对
        if lst[i]<lst[i-1]:
            #交换逆序
            lst[i],lst[i-1]=lst[i-1],lst[i]
            swap = True
    return swap

def bubbleSort(lst):
    lstLen=len(lst)
    #单元素列表已经是有序的
    if (lstLen<=1):
        return
    #只剩lst[len-1]时，数组已经是有序，不需要更多的比较
    for i in range(0,lstLen-1):
        swap=bubble(lst,i,lstLen-1)
        if not swap:
            print("finish when times=",i+1)
            break
    
lst = [1,11,2,22,3,33,-1,2,3]
print(bubble(lst,0,len(lst)-1))
print(lst)

bubbleSort(lst)
print(lst)

lst = [-1, 1, 2, 2, 3, 3, 11, 22, 33]
bubbleSort(lst)
print(lst)
